package com.example.algorithm.tree.heap;

import java.util.concurrent.locks.ReentrantReadWriteLock;

public class Heap<T extends Comparable<T>> {
    //存储堆中的元素
    private T[] items;
    //记录堆中的个数
    private int N;

    public Heap(int capacity) {
        this.items = (T[]) new Comparable[capacity+1];
        this.N = 0;
    }

    private ReentrantReadWriteLock rw = new ReentrantReadWriteLock();

    private ReentrantReadWriteLock.ReadLock readLock = rw.readLock();

    private ReentrantReadWriteLock.WriteLock writeLock = rw.writeLock();

    /**
     * 判断索引i处的值是否小于索引j处的值
     *
     * @param i
     * @param j
     * @return
     */
    private boolean less(int i, int j) {

        readLock.lock();

        try {
            return items[i].compareTo(items[j]) < 0;
        } finally {
            readLock.unlock();
        }
    }

    /**
     * 交换i，j的元素
     *
     * @param i
     * @param j
     */
    private void exch(int i, int j) {

        writeLock.lock();

        try {
            T temp = items[i];
            items[i] = items[j];
            items[j] = temp;
        } finally {
            writeLock.unlock();
        }
    }

    /**
     * 插入一个元素
     *
     * @param t
     */
    public void insert(T t) {

        writeLock.lock();

        try {
            items[++N] = t;
            swim(N);
        } finally {
            writeLock.unlock();
        }
    }

    /**
     * 使用上浮算法，使索引k处的元素处于堆中有序的位置
     *
     * @param k
     */
    private void swim(int k) {
        //通过循环，不断比较当前结点的值和父结点的值，如果父结点小，则交换位置
        while (k > 1) {
            //比较当前结点和其父节点
            if (less(k / 2, k)) {
                exch(k / 2, k);
            }
            k = k / 2;
        }
    }

    /**
     * 删除堆中最大的元素
     */
    public T delMax() {
        T max = items[1];
        //交换最大，和N处的值
        exch(1, N);
        items[N] = null;
        N--;
        //堆下沉调整堆
        sink(1);
        return max;
    }

    /**
     * 堆下沉
     *
     * @param k
     */
    public void sink(int k) {
        //不断对比k和k结点的2k和2k+1的大小
        while (2 * k <= N) {
            int max;
            if (2 * k + 1 <= N) {
                if (less(2 * k, 2 * k + 1)) {
                    max = 2 * k + 1;
                } else {
                    max = 2 * k;
                }
            } else {
                max = 2 * k;
            }

            if (!less(k,max)){
                break;
            }

            exch(k,max);

            k = max;
        }
    }

}